Masala #1033

Xotira 64 MB Vaqt 1250 ms Qiyinchiligi 45 %

3.0 (Baholar 4)

Kill the monsters!

“Kill the monsters!” nomli o‘yin mavjud. Bu o‘yinda, siz tushunib ulgurganingizdek, monsterlar bor va ularni o‘ldirish lozim.

O‘yin maydoni bitta uzun kesma bo‘lib, u $-10^9$ dan $10^9$ gacha raqamlangan koordinatalardan iborat. Koordinata 3 xil holatda bo‘lishi mumkin: koordinata bo‘sh, koordinatada 1 ta monster bor yoki koordinatada 1 ta devor bor. Maydondagi jami devorlar va monsterlar soni $n$ ga teng. Har bir monster o‘zining sog‘lik darajasiga ega.

Siz $k$ marta quyidagi ishni qila olasiz:

o‘yin maydonida devor bo‘lmagan va oldin belgilanmagan koordinatani tanlash va uni belgilash

So‘ng barcha belgilangan koordinatalarda bir vaqtda olov yoqasiz.

Qaysidir koordinatada olov yongan bo‘lsa, 1 soniyada shu koordinatadagi monsterning sog‘lik darajasi 1 birlikka kamayadi, hamda olov oldin yonmagan va devori yo‘q bo‘lgan qo‘shni koordinataga ham o‘tadi. Olov yongan koordinatada u hech qachon o‘chmaydi. Monsterning sog‘lik darajasi 0 ga tushsa, u o‘ldi deb hisoblanadi.

Yondirish uchun $k$ ta koordinatani optimal tanlab ularni yondirgach, eng kami bilan necha soniyadan so‘ng barcha monsterlar o‘lishini toping.

Optimal tanlovda ham, $10^{100}$ soniyadan so‘ng tirik monster topilsa, “IMPOSSIBLE” so‘zini qo‘shtirnoqlarsiz chiqaring.

Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida ikkita butun sonlar - $n,k(1 \le k \le n \le 2*10^5)$ kiritiladi.

Keyingi $n$ ta qatorning har birida maydondagi bo‘shmas kataklar ko‘rsatiladi.

Monster uchun yangi qatorda ‘M’ belgisi va yana 2 ta butun son - $x(-10^9 \le x \le 10^9)$ monster turgan koordinata va $h(1 \le h \le 10^9)$ monsterning sog‘lik darajasi kiritiladi.

Devor uchun yangi qatorda ‘W’ belgisi va yana 1 ta butun son - $x(-10^9 \le x \le 10^9)$ devor turgan koordinata kiritiladi.

Barcha testlar tepadagi shartlarni qanoatlantirishi kafolatlanadi.

Chiquvchi ma'lumotlar:

Yagona qatorda masala javobini chiqaring.

Misollar

#	input.txt	output.txt
1	3 2 M 1 4 W 2 M 3 6	6
2	3 1 M 1 4 W 2 M 3 6	IMPOSSIBLE
3	2 1 M -1000000000 1 M 1000000000 2	1000000002

Izoh:

Birinchi testda:

1 koordinatada sog‘ligi 4 bo‘lgan monster bor.
2 koordinatada devor bor.
3 koordinatada sog‘ligi 6 bo‘lgan monster bor.

Yondirish uchun 2 ta koordinatani belgilash lozim. 1 va 3 koordinatani belgilab ularni yondirsak, 6 soniyada barcha monsterlar o‘ladi. Bu eng yaxshi natija ekanligini isbotlasa bo‘ladi.

Ikkinchi testda:

Devor va monsterlar xuddi birinchi testdagidek, yagona farqi yondirish uchun faqatgina 1 ta koordinatani tanlash mumkin. Bu holatda javob “IMPOSSIBLE”. Chunki qaysi koordinatani yondirmaylik, bitta monster o‘ladi, boshqa monster esa devor sababli $10^{100}$ soniyadan so‘ng ham tirik qoladi.

Uchinchi testda:

Faqatgina 1 ta koordinatani yondirish mumkin. 0 koordinatani tanlash optimal bo‘ladi. Bunda 1-monsterga yetib olib uni o‘ldirish uchun $10^9+1$ soniya vaqt kerak. 2-monsterga yetib olib uni o‘ldirish uchun esa $10^9+2$ soniya vaqt kerak. Jami $10^9+2$ soniyadan so‘ng barcha monsterlar o‘lgan bo‘ladi.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin